package com.yulongtian.weekCompetition.month202301.week01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 可
 *
 * @author yulongTian
 * @create 2023-01-01 17:01
 */
public class Test04 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(closestPrimes(10, 20)));
    }

    public static int[] closestPrimes(int left, int right) {
        //left~right的质数
        List<Integer> zhi = getZhi(left, Math.min(left + 500, right));
        //只有一个质数
        if (zhi.size() <= 1) {
            return new int[]{-1, -1};
        }

        if (zhi.get(0) == 2 && zhi.get(1) == 3) {
            return new int[]{2, 3};
        }


        int[] dif = new int[zhi.size() - 1];

        for (int i = 1; i < zhi.size(); i++) {
            dif[i - 1] = zhi.get(i) - zhi.get(i - 1);
        }

        int min = dif[0];
        int ansIndex = 0;
        for (int i = 0; i < dif.length; i++) {
            if (dif[i] < min) {
                min = dif[i];
                ansIndex = i;
            }
        }

        return new int[]{zhi.get(ansIndex), zhi.get(ansIndex + 1)};
    }

    //计算left~right的质数
    public static List<Integer> getZhi(int left, int right) {
        List<Integer> ans = new ArrayList<>();
        int[] flags = new int[right + 1];
        flags[1] = 1;
        int k = 2;
        while (k * k < right + 1) {
            if (flags[k] == 0) {
                int k1 = k * k;
                while (k1 < right + 1) {
                    flags[k1] = 1;
                    k1 += k;
                }
            }
            k++;
        }

        for (int i = left; i < right + 1; i++) {
            if (flags[i] == 0) {
                ans.add(i);
            }
        }

        return ans;
    }

}


